/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 哈希表
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> fatherMap = new HashMap<>();
        Set<TreeNode> fatherSet = new HashSet<>();
        addFatherMap(root, fatherMap);
        
        TreeNode cur = p;
        while(cur != fatherMap.get(cur)){
            fatherSet.add(cur);
            cur = fatherMap.get(cur);
        }
        cur = q;
        while(cur != null){
            if(fatherSet.contains(cur)){
                return cur;
            }
            cur = fatherMap.get(cur);
        }
        return null;
    }
    public void addFatherMap(TreeNode root, Map<TreeNode,TreeNode> fatherMap){
        if(root == null){
            return ;
        }
        if(root.left != null){
            fatherMap.put(root.left, root);
            addFatherMap(root.left, fatherMap);
        }
        if(root.right != null){
            fatherMap.put(root.right, root);
            addFatherMap(root.right, fatherMap);
        }

    }
    // 递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root == null || p == root || q == root){
           return root;
       }
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
       return left != null ? left : right;
    }
}